<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3018：[Usaco2012 Nov]Distant Pastures</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2012 Nov]Distant Pastures</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2012 Nov]Distant Pastures</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Usaco2012 Nov]Distant Pastures                </h1>
                <p>时间限制：5s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div style="text-indent: 21pt"><span style="font-size: medium">Farmer John's farm is made up of an N x N grid of pastures, where each pasture contains one of two different types of grass. To specify these two types of grass, we use the characters ( and ), so for example FJ's farm might look like the following grid: </span></div>
<div><span style="font-size: medium">(())</span></div>
<div><span style="font-size: medium">)()(</span></div>
<div><span style="font-size: medium">)(((</span></div>
<div><span style="font-size: medium">))))</span></div>
<div style="text-indent: 21pt"><span style="font-size: medium">When Bessie the cow travels around the farm, it takes her A units of time to move from a pasture to an adjacent pasture (one step north, south, east, or west) with the same grass type, or B units of time to move to an adjacent pasture with a different grass type. Whenever Bessie travels from one pasture to a distant pasture, she always uses a sequence of steps that takes the minimum amount of time. Please compute the greatest amount of time Bessie will ever need to take while traveling between some pair of pastures on the farm.</span></div>
<div><span style="font-size: medium">&nbsp;</span></div>
<div><span style="font-size: medium">问题描述</span></div>
<div style="text-indent: 21pt"><span style="font-size: medium">给定一个<i>n</i>&times;<i>n</i>的一个网格，每个格子有一个字符，要么是&rsquo;(&lsquo;，要么是&rsquo;)&rsquo;。每个格子和它的上下左右的四个格子相邻，对于相邻的两个格子<i>x</i>和<i>y</i>，从<i>x</i>走到<i>y</i>的过程中，如果<i>x</i>和<i>y</i>中的字符相同，消耗<i>A</i>单位时间，如果<i>x</i>和<i>y</i>中字符不同，消耗<i>B</i>单位时间。定义点<i>S</i>到点<i>T</i>的时间为<i>D</i>(<i>S</i>,<i>T</i>)，现在想请你求出网格中最大的<i>D</i>(<i>S</i>,<i>T</i>)。</span></div>
<div><span style="font-size: medium">&nbsp;</span></div></p><hr/><h3>输入格式</h3><p><div><span style="font-size: medium">第一行三个整数<i>n</i>，<i>A</i>，<i>B</i>；</span></div>
<div><span style="font-size: medium">接下来<i>n</i>行描述这个<i>n</i>&times;<i>n</i>的网格。</span></div>
<div>1 &lt;= n &lt;= 30，1 &lt;= A &lt;= 1,000,000，1 &lt;= B &lt;= 1,000,000。</div></p><hr/><h3>输出格式</h3><p><div>&nbsp;</div>
<div><span style="font-size: medium">&nbsp;一个整数，最大的<i>D</i>(<i>S</i>,<i>T</i>)。</span></div>
<div><span style="font-size: medium">&nbsp;</span></div></p><hr/><h3>样例输入</h3><pre>3 1 2
(((
()(
(()</pre><hr/><h3>样例输出</h3><pre>5
 样例说明
左上角到右下角所需的时间为5，是最大值</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>Silver</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3018" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3018" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>